A typical computer operating system includes a variety of different resources ("objects"), such as data storage devices, programs, modems and hardware (e.g., printing devices). Each of these objects may be accessed by system users through one or more limited access permissions ("modes"). For example, a user may read information stored in a data file by means of a "read" mode, and may add information to, or delete information from, the data file by means of "write" and "delete" modes, respectively. Similarly, a "copy" mode allows a user to copy a program or file, while an "execute" mode allows a user to use the program or file, but not copy it.
In a multi-user environment, it is desirable to control access to the available system objects among the plurality of users, such that some of the objects are "open" (i.e., accessible to all users in all available modes) while others are "secure" (i.e., accessible to only a predetermined segment of the user population).
In very simple systems, each user is provided a respective "identifier" or "password", while each of the secure objects has an associated "tag" or "information node" which identifies, among other things, the single user to which the object belongs. Thus, only the user that "owns" the object may gain access to it.
However, in modern computer systems it is common for different users to share secure objects among themselves. For example, a user may wish to selectively allow other users to read, write or delete, etc., a secure object that he or she owns. A common method of allowing or denying access to each secure object on a per-user basis is through the use of "classical" access control list implementations.
As shown in FIG. 1A, a first implementation of an access control list may comprise a matrix defining the set of users and the set of available objects, with appropriate access permissions indicated at predetermined addresses of the matrix. Thus, in accordance with the access control matrix of FIG. 1A, USER1 can access OBJECT2 with "write" permission only, USER2 can access OBJECT1 with "read", "write" or "execute" permission, and so on.
As alternatives to an access control matrix, user-based access control lists (FIG. 1B)--which associates with each user a list of objects that the user can access, and with what permission--and object-based access control lists (FIG. 1C)--which associate with each object a list of users that may access that object, and with what permissions--have been utilized.
While the above-described "classical" access control lists are effective means for controlling access to secure objects in multi-user systems, they are expensive to implement since both computer time and data storage space are very expensive. The matrix implementation of FIG. 1A is attractive timewise since the time needed to locate a unique matrix address is very small, but is not efficient spacewise. Since most users in a "secure" system do not have access to most files, many of the entries in an access control matrix are blank. This is very inefficient.
In contrast, the individual list implementations of FIGS. 1B and 1C are attractive spacewise since "blank" entries are not stored, but are inefficient timewise since list searching is, by its very nature, more time consuming than the simple address calculation offered by the matrix implementation. In short, the two "classical" implementations of access control lists offer a time/space trade-off.
Furthermore, adding a user or object in these "classical" implementations requires creation of either a new list or matrix row/column, and modifying access permissions requires matrix update or list manipulation. All of these actions require significant computational overhead.